1. Field of the Invention
The present invention relates to a calculating circuit for error correction, and more particularly to a multiple division circuit for carrying out Euclidean mutual division.
2. Description of the Prior Art
In the implementation of an error-correcting system using an error-correcting code represented by a Bose-Chaundhuri-Hocquenghem (BCH) code or a Reed-Solomon code, a means for determining an error locator polynomial from a syndrome generated from a received signal plays the most important role (see "7R-C601-018(4740) Hardware implementation of a high-speed multiple error-correcting circuit using the Reed-Solomon code (1)").
One well known process for determining such an error locator polynomial uses an Euclidean mutual division algorithm (see "7R-C601-020(4788) Hardware implementation of a high-speed multiple error-correcting circuit using the Reed-Solomon code (2)").
The Euclidean mutual division method is generally known as an algorithm for obtaining the most common divisors of two polynomials. In the error-correcting code, an error locator polynomial can be calculated from a syndrome by the skillful application of a calculation using the Euclidean mutual division method.
The calculation using the Euclidean mutual division method is advantageous in that it can be composed of a systolic-array architecture which can be realized by cascading a plurality of relatively simple calculation units (hereinafter referred to as "mutual division units").
Howard M. Shao, et. al. have proposed an example in which the Euclidean mutual division algorithm is implemented by a systolic-array architecture (see Howard M. Shao, et. al. "A VSLI Design of a Pipeline Reed-Solomon Decoder" IEEE Trans. on Computers Vol. C-34, May 1985). This method will hereinafter be referred to as a "method A". The method A however has defects in that its algorithm is not perfect and that each unit needs two multipliers for a finite field. Thus, when a system that needs high-speed real-time processing is to be constructed based on this method A, its circuit scale is increased.
We have previously proposed a method as an improvement of the method A as disclosed in U.S. patent application Ser. No. 07/623,235 filed Dec. 6, 1990. This proposed method will hereinafter be referred to as a "method B". The method B employs a revised Euclidean mutual division method (2) as disclosed in the above article by Howard M. Shao et. al., and replaces two finite field multipliers in the mutual division unit with a multiplier for a finite field and a divider for a finite field. Furthermore, in the method B, the finite field dividers used in a plurality of cascaded mutual division units are shared by a single divider for a finite field. The circuit arrangement used to implement the method B is therefore reduced in circuit scale.
We also have proposed an improved method (hereinafter referred to as a "method C") which is entirely different from the method B and employs only one additional circuit for sharing the divider and only one degree control circuit, as disclosed in Japanese patent application No. 3-254,183 filed Sep. 6, 1991. According to the method C, a circuit for sharing the divider and a control circuit therefor are not required because data to be divided can be extracted from one location at all times. In addition, a circuit for judging operation from the degree of a polynomial and a control circuit are realized by single circuits, respectively. Therefore, the method C can be implemented by a circuit arrangement of reduced circuit scale.
Now, the execution of only one calculation by one calculation unit in one step according to the revised Euclidean mutual division method (2) will be considered below. That is, the number of calculation units that are essentially required except when two or more calculations are carried out by one calculation unit through multiplexing such as time-division multiplexing will be considered below.
The numbers of calculation units required by the respective methods A, B, C are 8t, 4t, 4t-1, respectively. The numbers of calculation units required by the methods B and C are reduced to half the number of calculation units required by the method A. This is because one divider, rather than two multipliers, is used by each of the units, thereby reducing the number of multipliers required by respective calculation units to one.
While the number of calculations (multiplications) needed by the algorithm itself of the revised Euclidean mutual division method (2) is only 2t for one step, the circuit arrangement which implements the methods B and C requires as many calculation units as twice the number that is essentially required by the algorithm, and hence is wasteful. Similarly, the number of registers required to store the coefficients of polynomials is about twice the number that is essentially required by the algorithm.